package sort

/*
	平均时间复杂度：O(nlogn)
	最好情况：O(nlogn)
	最坏情况：O(nlogn)
	空间复杂度：O(n)
	排序方式：Outplace
	稳定性：稳定
*/
func MergeSort(nums []int) []int {
	if len(nums) < 2 {
		return nums
	}

	mid := len(nums) / 2

	result := merge(nums[:mid], nums[mid:])
	return result
}

func merge(left []int, right []int) []int {

	result := []int{}

	if len(left) >= 2 {
		left_mid := len(left) / 2
		left = merge(left[:left_mid], left[left_mid:])
	}

	if len(right) >= 2 {
		right_mid := len(right) / 2
		right = merge(right[:right_mid], right[right_mid:])
	}

	for len(left) != 0 && len(right) != 0 {
		if left[0] < right[0] {
			result = append(result, left[0])
			left = left[1:]
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}

	if len(left) != 0 {
		result = append(result, left...)
	}
	if len(right) != 0 {
		result = append(result, right...)
	}

	return result
}
